package dp.test32;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/22 11:12
 */
public class Solution1 {
    public int longestValidParentheses(String s) {
        if (s == null || s.equals("")) return 0;
        int n = s.length();
        int[] dp = new int[n];
        int maxL = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') continue;
            else {
                if (i > 0 && s.charAt(i - 1) == '(') {
                    dp[i] = i - 1 > 0 ? dp[i - 2] + 2 : 2;
                } else if (i > 0 && s.charAt(i - 1) == ')') {
                    if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] + dp[i - 1] + 2 : dp[i - 1] + 2;
                    }
                }
            }
            if (dp[i] > maxL) maxL = dp[i];
        }
        return maxL;
    }
}
